La respuesta es

\binom{m}{k} · ∑_{i=0}^{m−k}(−1)^{i}\binom{m − k}{i}(n − k − i)!

Explicación: Lo primero que hacemos es escoger los k elementos que quedarán “clavados” en su sitio correcto. Esto se puede hacer de \binom{m}{k} maneras diferentes, pues cualquier subconjunto de k elementos entre los primeros m elementos sirve para este propósito.

Ahora bien, por cada una de estas clavadas nos quedan n − k elementos por ubicar. Hay que hacerlo de manera que en las primeras m−k posiciones ningún elemento quede en su sitio, porque si sucede lo contrario entonces habrá mas elementos clavados en su sitio de los k pedidos. Para contar cuántas permutaciones de n − k elementos cumplen esto, utilizamos el principio de inclusión-exclusión^{1}. El resultado es la sumatoria que multiplica a \binom{m}{k}.

Demostración. Decimos que una permutación tiene la propiedad P_{i} si deja en su sitio el elemento i. El número que se busca es el número de permutaciones de n − k elementos que no tiene la propiedad P_{i} para i = 1, 2, ⋯, m − k y lo denotamos D = N(P̄_{1}P̄_{2} ⋯ P̄_{m−k}). Aplicando el principio de inclusión-exclusión tenemos que:

D = N − ∑_{i} N(P_{i}) + ∑_{i<j} N(P_{i}P_{j}) − ∑_{i<j<k} N(P_{i}P_{j}P_{k}) + ⋯ + (−1)^{m−k}N(P_{1}P_{2} ⋯ P_{m−k})

Vemos que

N = (n − k)!

pues N es la cantidad de permutaciones posibles. Así mismo,

∑_{i} N(P_{i}) = \binom{m − k}{1}(n − k − 1)!

Esto es, clavamos un sólo elemento de los primeros m − k posibles, y el resto los permutamos de cualquier manera posible. Pero al restar estos elementos, restamos dos veces las permutaciones que tienen dos elementos fijos, así que las volvemos a sumar:

∑_{i<j} N(P_{i}P_{j}) = \binom{m − k}{2}(n − k − 2)!

Esto es, clavamos dos elementos y el resto los permutamos de cualquier manera posible. Y en general,

∑ N(P_{i_{1}}P_{i_{2}} ⋯ P_{i_{r}}) = \binom{m − k}{r}(n − k − r)!

Reemplazando estos términos en la ecuación original, obtenemos

D = N − ∑_{i} N(P_{i}) + ∑_{i<j} N(P_{i}P_{j}) − ∑_{i<j<k} N(P_{i}P_{j}P_{k}) + ⋯ + (−1)^{m−k}N(P_{1}P_{2} ⋯ P_{m−k})

= (n - k)! - m - k (_{1(n−k−1)!+\binom{m−k}{2}(n−k−2)!−···+(−1)^{m−k}\binom{m−k}{m−k}(n−k−(m−k))!})

= ∑_{i=0}^{m−k}(−1)^{i}\binom{m−k}{i}(n − k − i)!

1Bastante similar a la demostración del teorema 2, “Número de permutaciones completas”, Sección 6.6: Aplicaciones del principio de inclusión-exclusión, Capítulo 6: Técnicas avanzadas de recuento, página 430, del libro Matemáticas discretas y sus aplicaciones, Kenneth Rosen, quinta edición, McGraw-Hill.